#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string preprocess(const string& s) 
{
    string result = "^#";
    for(int i=0;i<s.size();i++)
	{
        result += s[i];
        result += '#';
    }
    result += "$";
    return result;
}

string longestPalindrome(const string& s) 
{
    string processed = preprocess(s);
    int n = processed.length();
    vector<int> P(n, 0);
    int center = 0, right = 0;

    for (int i = 1; i < n - 1; ++i) 
	{
        int mirror = 2 * center - i;

        if (i < right) 
		{
            P[i] = min(right - i, P[mirror]);
        }

        while (processed[i + 1 + P[i]] == processed[i - 1 - P[i]]) 
		{
            P[i]++;
        }

        if (i + P[i] > right) 
		{
            center = i;
            right = i + P[i];
        }
    }

    int maxLen = 0, centerIndex = 0;
    for (int i = 1; i < n - 1; ++i) 
	{
        if (P[i] > maxLen) 
		{
            maxLen = P[i];
            centerIndex = i;
        }
    }

    return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
}

int main() {
    string s = "babad";
    cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;

    return 0;
}

